package geography;

import java.awt.Dimension;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Stack;

import structure.MazeNode;

public class Maze {
	private static Random random = new Random();
	private int xSize;
	private int ySize;
	private MazeNode[][] tiles;
	private MazeNode startingNode;
	private MazeNode exitNode;

	private List<MazeNode> endingNodes;
	
	private int totalCells = 0;
	private int visitedCells = 0;
	private boolean[][] cellVisited;
	private Stack<MazeNode> nodeStack;
	
	/**
	 * Creates and initializes a maze with a certain width and height.
	 * @param width {@link Integer} Width, must be greater than 5.
	 * @param height {@link Integer} Height, must be greater than 5.
	 * @throws Exception if the size is smaller than 5x5.
	 */
	public Maze(int width, int height) throws Exception{
		if(width < 5 || height < 5){
			throw new Exception("Maze is too small.");
		}
		xSize = width;
		ySize = height;
		
		totalCells = width*height;
		
		tiles = new MazeNode[width][height];
		cellVisited = new boolean[width][height];
		
		for(int i=0;i<xSize;i++){
			for(int j=0;j<ySize;j++){
				tiles[i][j] = new MazeNode(i, j);
				
				cellVisited[i][j] = false;
			}
		}
		nodeStack = new Stack<MazeNode>();
		
		endingNodes = new ArrayList<MazeNode>();;
		
		createRandomizedMaze();		
	}
	/**
	 * Creates and initializes a maze with a certain width and height.
	 * @param width {@link Integer} Width, must be greater than 5.
	 * @param height {@link Integer} Height, must be greater than 5.
	 * @throws Exception if the size is smaller than 5x5.
	 */
	public Maze(Dimension dim) throws Exception{
		this(dim.width, dim.height);
	}
	
	/**
	 * Returns the size of the maze.
	 * @return {@link Dimension} corresponding to the maze's size.
	 */
	public Dimension getDimensions(){
		return new Dimension(xSize, ySize);
	}
	
	/**
	 * Returns a reference to an array containing all the {@link MazeNode}-objects in this maze.
	 * @return An array of {@link MazeNode}-objects in their finished (maze-calculated) state.
	 */
	public MazeNode[][] getTiles(){
		return tiles;
	}
	
	//initializes the creation of the maze
	//the algorithm used is an implementation of Depth-First-Search
	private void createRandomizedMaze(){
		int startPosX, startPosY;
		
		//maze starts randomly at any of the four edges
		int dice = random.nextInt();
		if(dice%4 == 0){
			startPosX = random.nextInt(xSize);
			startPosY = 0;
		}
		else if(dice%4 == 1){
			startPosX = random.nextInt(xSize);
			startPosY = ySize-1;
		}
		else if(dice%4 == 2){
			startPosX = 0;
			startPosY = random.nextInt(ySize);
		}
		else{
			startPosX = xSize-1;
			startPosY = random.nextInt(ySize);
		}
		
		//starting-position is noted
		startingNode = tiles[startPosX][startPosY];
		//begin building the maze from this node		
		buildMaze(startingNode);
		
		//creates random connections to establish loops in the maze
		//the parametre determines the amount of new connections made in relation to the maze's width
		createRandomCircles(3);
		placeExit();
	}
	
	/**
	 * Returns the starting-position of this maze.
	 * @return {@link Location} where the maze begins, or {@code null} if no starting-position is set.
	 */
	public Location getStartingLocation(){
		if(startingNode == null){
			return null;
		}
		return startingNode.getLocation();
	}
	/**
	 * Returns the location of the maze's exit.
	 * @return {@link Location}
	 */
	public Location getExitLocation(){
		if(exitNode == null){
			return null;
		}
		return exitNode.getLocation();
	}
	
	//recursively builds the maze from the starting-node
	private void buildMaze(MazeNode startNode){
		//initial node is checked off
		MazeNode currentNode = startNode;
		setVisited(currentNode.getLocation());
		visitedCells++;
		
		//as long as unvisited cells remain
		while(visitedCells < totalCells){
			//a random neighbouring node, which has not been visited, is picked
			MazeNode randomNeighbour = getRandomNeighbour(currentNode);
			if(randomNeighbour != null){
				//a connection is created and the process continues with the new node, the old node is put on the stack
				makePassage(currentNode, randomNeighbour);
				MazeNode tempNode = currentNode;
				nodeStack.add(tempNode);
				currentNode = randomNeighbour;
				visitedCells++;
			}
			else{
				//the last node is taken from the stack and the algorithm continues where it left off
				currentNode = nodeStack.pop();
			}
		}
		
	}
	
	//returns a random neighbouring node, which has not been visited yet, or null
	private MazeNode getRandomNeighbour(MazeNode target){
		Location currentLocation = target.getLocation();
		int currentX = currentLocation.getX(), currentY = currentLocation.getY();
		List<MazeNode> neighbourList = new ArrayList<MazeNode>();
		
		//adds all availabe neighbours to the list
		if(currentX > 0){
			if(cellVisited[currentX-1][currentY] == false){
				neighbourList.add(tiles[currentX-1][currentY]);
			}
		}
		if(currentX < xSize-1){
			if(cellVisited[currentX+1][currentY] == false){
				neighbourList.add(tiles[currentX+1][currentY]);
			}
		}
		if(currentY > 0){
			if(cellVisited[currentX][currentY-1] == false){
				neighbourList.add(tiles[currentX][currentY-1]);
			}
		}
		if(currentY < ySize-1){
			if(cellVisited[currentX][currentY+1] == false){
				neighbourList.add(tiles[currentX][currentY+1]);
			}
		}
		if(neighbourList.isEmpty()){
			return null;
		}
		
		MazeNode returnNode = neighbourList.get(random.nextInt(neighbourList.size()));
		
		return returnNode;
	}
	
	//connects two nodes and marks the target-node as visited
	private void makePassage(MazeNode origin, MazeNode target){
		
		Location originLocation = origin.getLocation();
		int originX = originLocation.getX(), originY = originLocation.getY();
		
		Location targetLocation = target.getLocation();
		int targetX = targetLocation.getX(), targetY = targetLocation.getY();
		
		setVisited(targetLocation);
		
		//sets the connection between the two nodes
		if(originX == targetX){
			if(originY > targetY){
				origin.setNorth(target);
				target.setSouth(origin);
			}
			else{
				origin.setSouth(target);
				target.setNorth(origin);
			}
		}
		else{
			if(originX > targetX){
				origin.setWest(target);
				target.setEast(origin);
			}
			else{
				origin.setEast(target);
				target.setWest(origin);
			}
		}
	}
	
	//checks a location off as visited
	private void setVisited(Location nodeLocation){
		int x = nodeLocation.getX(), y = nodeLocation.getY();
		cellVisited[x][y] = true;
	}
	
	//since the DFS-algorithm creates no edges looping back in the graph, we create random connections to make the maze less linear in its branches
	private void createRandomCircles(int factor){
		int counter = xSize*factor, randomX, randomY;
		boolean connectionSuccessful;
		MazeNode currentNode = null;
		while (counter > 0) {
			//a random location is chosen that is not on one of the edges
			randomX = random.nextInt(xSize-2)+1;
			randomY = random.nextInt(ySize-2)+1;
			
			currentNode = tiles[randomX][randomY];
			
			connectionSuccessful = makeNewConnection(currentNode);
			if(connectionSuccessful){
				counter--;
			}			
		}
	}
	
	private boolean makeNewConnection(MazeNode target){
		Location currentLocation = target.getLocation();
		int currentX = currentLocation.getX(), currentY = currentLocation.getY();
		
		if(target.isDisconnected()){
			//target is an isolated node
			return false;
		}
		//a random direction is chosen and a connection established if possible
		int dice = random.nextInt(4);
		switch (dice) {
		case 0:
			if(target.getNorth() == null && currentY > 0){
				makePassage(target, tiles[currentX][currentY-1]);
				return true;
			}
			return false;
		case 1:
			if(target.getEast() == null && currentX < xSize-1){
				makePassage(target, tiles[currentX][currentY-1]);
				return true;
			}			
			return false;
		case 2:
			if(target.getSouth() == null && currentY < ySize-1){
				makePassage(target, tiles[currentX][currentY-1]);
				return true;
			}
			return false;
		case 3:
			if(target.getWest() == null && currentY > 0){
				makePassage(target, tiles[currentX][currentY-1]);
				return true;
			}	
			return false;
		default:
			return false;
		}		
	}
	
	
	private void placeExit(){
		if(startingNode == null){
			return;
		}
		int x = startingNode.getLocation().getX(), y = startingNode.getLocation().getY();
		int xNew = Math.abs(x-(xSize-1)), yNew = Math.abs(y-(ySize-1));
		if(x == 0 || x == xSize-1){
			 getDeadEnds(xNew, "y");
		}
		else{
			getDeadEnds(yNew, "x");
		}
		
		exitNode = endingNodes.get(random.nextInt(endingNodes.size()));
	}
	
	private void getDeadEnds(int start, String direction){
		if(direction == "y"){
			for(int k=0;k<(xSize/2)-1;k++){
				int j = Math.abs(start-k);
				for(int i=0;i<tiles[j].length;i++){					
					if(tiles[j][i].isDeadEnd()){
						endingNodes.add(tiles[j][i]);
					}					
				}
			}
			
			
		}
		else{
			for(int k=0;k<(ySize/2)-1;k++){
				int j = Math.abs(start-k);
				for(int i=0;i<tiles.length;i++){					
					if(tiles[i][j].isDeadEnd()){
						endingNodes.add(tiles[i][j]);
					}					
				}
			}
		}
	}
	
	/**
	 * Returns a {@link String}-representation of the maze.
	 */
	public String toString(){
		String output = "";
		
		for(int j=0;j<ySize;j++){
			
			for(int i=0;i<xSize;i++){
				if(tiles[i][j].getNorth() != null){
					output += "  |  ";
				}
				else{
					output += "     ";
				}
			}
			output += "\n";

			for(int i=0;i<xSize;i++){
				if(!tiles[i][j].isDisconnected()){
					if(tiles[i][j].getWest() != null){
						output += "--";
					}
					else{
						output += "  ";
					}
					output += "O";
					if(tiles[i][j].getEast() != null){
						output += "--";
					}
					else{
						output += "  ";
					}
				}
				else{
					output += "     ";
				}
				
			}
			output += "\n";
			
		}
		
		return output;
	}
	
	
}
